from random import randrange
import math
#rsa
##选择素数
def init_prime(n:int):
    flag=1
    while flag==1:
        assert n>1
        p=randrange(2**(n-1)+1,2**n,2)
        if __miller_rabin(p,8):flag=0;return p;
##米勒拉宾算法验证是否是素数
def __miller_rabin(p,round):
    if p==1:return False;#1不是素数
    if p==2:return True;#2是素数
    if p>3 and p%2==0:return False;#2的倍数都不是素数
    s,d=0,p-1;
    while d%2==0:
        d>>=1;s+=1;
    for _ in range(round):
        a=randrange(2,p-1)
        x=pow(a,d,p)
        if x==1 or x==p-1:
            continue
        for _ in range(s):
            x=pow(x,2,p)
            if x==p-1:
                break
        else:return False
    return True;

#扩展欧几里得算法
def exgcd(a,b):
    if(b==0):
        return 1,0,a;
    else:
        x,y,gcd=exgcd(b,a%b);
        x,y=y,(x-(a//b)*y);
    return x,y,gcd
#求模反元素
def mod_inverse(fn,x):
     while x<0:
        x = (x + fn) % fn
     return x


#1.选择一对不相等且足够大的质数p和q（生成素数，并验证pq是否为质数）
#2.计算pq的乘积n
#3.计算n的欧拉函数=（p-1）（q-1）
#4.选一个与n的欧拉函数互质的整数e，1<e<（q-1）（p-1）
#5.计算e对于（p-1）（q-1）的模反元素d，de mod （p-1）（q-1）=1
#6.公钥：ku=（e,n）
#7.密钥：kr=（d,n）
def keys(n,accurate: bool = True, poolsize: int = 1, e=65537):
    p=init_prime(n);q=init_prime(n);
    print("p=",p)
    print("q=",q)
    while p==q:
        q=init_prime(n);
    N=p*q;
    ffn=(p-1)*(q-1);
    #d=mod_inverse(e,ffn);
    d,_,_=exgcd(e,ffn)
    d = mod_inverse(ffn,d);
    print("p=",p,"q=",q)
    print("N=",N,"e=",e,"d=",d)
    return [N,e],[N,d]


#加密:M^e mod n=C
def encrypt(message,uk):
    secret=[]
    for i in message:
        secret.append(quick_pow_mod(i,uk[1],uk[0]))
    return secret
# 解密：C^d mod n =M
def decrypt(message,pk):
    ming=[];
    for i in message:
        ming.append(quick_pow_mod(i,pk[1],pk[0]));
    return bytes(ming)
def quick_pow_mod(a, e, n):
    ans = 1
    while e != 0:
        if e & 1:
            ans = (ans * a) % n
        e >>= 1
        a = a * a % n
    return ans

uk,pk=keys(48);
print("公钥为",uk);
print("私钥为",pk);
test1="shenqiqi";test2="12345678"
etest1=encrypt(test1.encode("utf-8"),uk);
etest2=encrypt(test2.encode("utf-8"),uk);
print(test1,"加密结果为：",etest1);
print(test2,"加密结果为：",etest2);
dtest1=decrypt(etest1,pk);
dtest2=decrypt(etest2,pk);
print("解密结果为：",dtest1.decode("utf-8"));
print("解密结果为：",dtest2.decode("utf-8"));


